import functools
class Solution(object):
    def countArrangement(self, n):
        """
        :type n: int
        :rtype: int
        """
        DP = [set() for _ in range(n)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    DP[i - 1].add(j - 1)
                    DP[j - 1].add(i - 1)
        @functools.cache
        def search(value, k):
            if k == n:
                return 1
            t = 0
            for num in DP[k]:
                if (value >> num) & 1:
                    t += search(value - (1 << num), k + 1)
            return t

        return search(2 ** n - 1, 0)



data = Solution()
n = 2
print(data.countArrangement(n))
